package com.zq.solution;

/**
 * @ClassName CountPrimes
 * @Description
 * 204. 计数质数
 *   统计所有小于非负整数n的质数的数量。
 * 示例 1：
 *   输入：n = 10
 *   输出：4
 *   解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * 示例 2：
 *   输入：n = 0
 *   输出：0
 * 示例 3：
 *   输入：n = 1
 *   输出：0
 * 提示：
 *   0 <= n <= 5 * 106
 * @Author ZQ
 * @Date 2020/12/3 9:17
 * @Version 1.0
 */
public class CountPrimes {
    public static int countPrimes(int n) {
        if (n <= 2)
            return 0;
        int sum = 0;
        for (int i = 2; i < n; i++){
            if (i % 2 == 0 && i != 2) continue;
            boolean isPrime = true;
            int t = (int)Math.sqrt(i);
            for (int j = 2; j <= t; j++){
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                sum++;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int n = countPrimes(100);
        System.out.println(n);
    }
}
